package find.the.repeat.number.two;

import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2019/12/27
 * @author 王光浩
 * @Need 给出一个整型数组以及一个整数k，在数组中寻找出下标差最小，且对应元素值相等的i、j，判断|i-j|是否大于k，如果大于
 *       返回false，否则返回true。
 * @Method 使用HashMap。key值为数组元素值，value为最近一次获取到key所对应的下标。
 *         思路：使用循环遍历数组将元素加入到HashMap中，并判断对应的元素值是否存在于HashMap中，如果存在则比较下标的绝对
 *               值与K的大小，如果小于则返回true，否则更新该value，如果不存在则将元素加入到HashMap。
 *               时间复杂度：O（n）——最坏情况下（不考虑数组扩容所造成的时间），空间复杂度：O（n）
 */
public class MyMethodTwo {
	 public boolean containsNearbyDuplicate(int[] nums, int k) {
		Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
		int len=nums.length;
		int tem=0;
		//循环遍历数组
		for(int i=0;i<len;i++) {
			if(hashMap.containsKey(nums[i])) {
				tem=i-hashMap.get(nums[i]);
				if(tem<=k)return true;
			}
			hashMap.put(nums[i], i); //如果存在则更新，否则添加
		}
		return false;
	 }
}
